package com.zlk.algorithm.algorithm.sort;

import org.junit.Test;

import java.util.Arrays;

/**
 * @program: algorithm
 * @ClassName Index
 * @description:  todo 排序总结
 * @author: slfang
 * @create: 2024-01-28 20:31
 * @Version 1.0
 **/
public class Index {

//稳定性
//原序列    1  1   2  1   2
// 排序后  1 1  1 2  2
//第一个1 还是再第一个1 位置  第一个2 还是再第二个2 位置之前

//                 时间复杂度	        额外空间复杂度		稳定性   解释见index.md
//    选择排序		O(N^2)			    O(1)		无         // 2 2 1  2 11   2经过第一次排序就再 第二个2 之后了
//    冒泡排序		O(N^2)			    O(1)		有
//    插入排序		O(N^2)			    O(1)		有
//    归并排序		O(N*logN)			O(N)		有
//    随机快排		O(N*logN)			O(logN)		无
//    堆排序		    O(N*logN)			O(1)		无(存在堆定与数组最后一个位置交换)
//========================================================
//    计数排序		O(N)			    O(Max)		有
//    基数排序		O(N)			    O(N)		有

//    优化：
//    插入排序  如希尔排序  二分插入排序
//    快速排序  三项取中
//    快排是堆排序归并排序插入排序  最快的，没有稳定性要求，优先考虑 快排
//
//  todo 随机快排 时间复杂度   加强堆改造

    @Test
    public void test(){
        int[] arr = new int[]{1211,312,12,0,11,12,1};
        // arrays 内部实现
        Arrays.sort(arr);
    }






}
